﻿using System;
using System.Collections.Generic;
using GeoAPI.Geometries;
using NetTopologySuite.Geometries;
using NetTopologySuite.Utilities;

namespace NetTopologySuite.Algorithm
{
	public class ConvexHull
	{
		public ConvexHull(IGeometry geometry) : this(ConvexHull.ExtractCoordinates(geometry), geometry.Factory)
		{
		}

		public ConvexHull(Coordinate[] pts, IGeometryFactory geomFactory)
		{
			this._inputPts = UniqueCoordinateArrayFilter.FilterCoordinates(pts);
			this._geomFactory = geomFactory;
		}

		private static Coordinate[] ExtractCoordinates(IGeometry geom)
		{
			UniqueCoordinateArrayFilter uniqueCoordinateArrayFilter = new UniqueCoordinateArrayFilter();
			geom.Apply(uniqueCoordinateArrayFilter);
			return uniqueCoordinateArrayFilter.Coordinates;
		}

		public IGeometry GetConvexHull()
		{
			if (this._inputPts.Length == 0)
			{
				return this._geomFactory.CreateGeometryCollection(null);
			}
			if (this._inputPts.Length == 1)
			{
				return this._geomFactory.CreatePoint(this._inputPts[0]);
			}
			if (this._inputPts.Length == 2)
			{
				return this._geomFactory.CreateLineString(this._inputPts);
			}
			Coordinate[] pts = this._inputPts;
			if (this._inputPts.Length > 50)
			{
				pts = ConvexHull.Reduce(this._inputPts);
			}
			Coordinate[] coordinates = ConvexHull.GrahamScan(ConvexHull.PreSort(pts)).ToArray();
			return this.LineOrPolygon(coordinates);
		}

		private static Coordinate[] Reduce(Coordinate[] pts)
		{
			Coordinate[] array = ConvexHull.ComputeOctRing(pts);
			if (array == null)
			{
				return pts;
			}
			HashSet<Coordinate> hashSet = new HashSet<Coordinate>();
			for (int i = 0; i < array.Length; i++)
			{
				hashSet.Add(array[i]);
			}
			for (int j = 0; j < pts.Length; j++)
			{
				if (!CGAlgorithms.IsPointInRing(pts[j], array))
				{
					hashSet.Add(pts[j]);
				}
			}
			Coordinate[] array2 = CoordinateArrays.ToCoordinateArray(hashSet);
			Array.Sort<Coordinate>(array2);
			if (array2.Length < 3)
			{
				return ConvexHull.PadArray3(array2);
			}
			return array2;
		}

		private static Coordinate[] PadArray3(Coordinate[] pts)
		{
			Coordinate[] array = new Coordinate[3];
			for (int i = 0; i < array.Length; i++)
			{
				if (i < pts.Length)
				{
					array[i] = pts[i];
				}
				else
				{
					array[i] = pts[0];
				}
			}
			return array;
		}

		private static Coordinate[] PreSort(Coordinate[] pts)
		{
			for (int i = 1; i < pts.Length; i++)
			{
				if (pts[i].Y < pts[0].Y || (pts[i].Y == pts[0].Y && pts[i].X < pts[0].X))
				{
					Coordinate coordinate = pts[0];
					pts[0] = pts[i];
					pts[i] = coordinate;
				}
			}
			Array.Sort<Coordinate>(pts, 1, pts.Length - 1, new ConvexHull.RadialComparator(pts[0]));
			return pts;
		}

		private static Stack<Coordinate> GrahamScan(Coordinate[] c)
		{
			Stack<Coordinate> stack = new Stack<Coordinate>(c.Length);
			stack.Push(c[0]);
			stack.Push(c[1]);
			if (c.Length > 2)
			{
				stack.Push(c[2]);
			}
			for (int i = 3; i < c.Length; i++)
			{
				Coordinate coordinate = stack.Pop();
				while (stack.Count > 0 && CGAlgorithms.ComputeOrientation(stack.Peek(), coordinate, c[i]) > 0)
				{
					coordinate = stack.Pop();
				}
				stack.Push(coordinate);
				stack.Push(c[i]);
			}
			stack.Push(c[0]);
			return stack;
		}

		private static bool IsBetween(Coordinate c1, Coordinate c2, Coordinate c3)
		{
			if (CGAlgorithms.ComputeOrientation(c1, c2, c3) != 0)
			{
				return false;
			}
			if (c1.X != c3.X)
			{
				if (c1.X <= c2.X && c2.X <= c3.X)
				{
					return true;
				}
				if (c3.X <= c2.X && c2.X <= c1.X)
				{
					return true;
				}
			}
			if (c1.Y != c3.Y)
			{
				if (c1.Y <= c2.Y && c2.Y <= c3.Y)
				{
					return true;
				}
				if (c3.Y <= c2.Y && c2.Y <= c1.Y)
				{
					return true;
				}
			}
			return false;
		}

		private static Coordinate[] ComputeOctRing(Coordinate[] inputPts)
		{
			Coordinate[] coord = ConvexHull.ComputeOctPts(inputPts);
			CoordinateList coordinateList = new CoordinateList();
			coordinateList.Add(coord, false);
			if (coordinateList.Count < 3)
			{
				return null;
			}
			coordinateList.CloseRing();
			return coordinateList.ToCoordinateArray();
		}

		private static Coordinate[] ComputeOctPts(Coordinate[] inputPts)
		{
			Coordinate[] array = new Coordinate[8];
			for (int i = 0; i < array.Length; i++)
			{
				array[i] = inputPts[0];
			}
			for (int j = 1; j < inputPts.Length; j++)
			{
				if (inputPts[j].X < array[0].X)
				{
					array[0] = inputPts[j];
				}
				if (inputPts[j].X - inputPts[j].Y < array[1].X - array[1].Y)
				{
					array[1] = inputPts[j];
				}
				if (inputPts[j].Y > array[2].Y)
				{
					array[2] = inputPts[j];
				}
				if (inputPts[j].X + inputPts[j].Y > array[3].X + array[3].Y)
				{
					array[3] = inputPts[j];
				}
				if (inputPts[j].X > array[4].X)
				{
					array[4] = inputPts[j];
				}
				if (inputPts[j].X - inputPts[j].Y > array[5].X - array[5].Y)
				{
					array[5] = inputPts[j];
				}
				if (inputPts[j].Y < array[6].Y)
				{
					array[6] = inputPts[j];
				}
				if (inputPts[j].X + inputPts[j].Y < array[7].X + array[7].Y)
				{
					array[7] = inputPts[j];
				}
			}
			return array;
		}

		private IGeometry LineOrPolygon(Coordinate[] coordinates)
		{
			coordinates = ConvexHull.CleanRing(coordinates);
			if (coordinates.Length == 3)
			{
				return this._geomFactory.CreateLineString(new Coordinate[]
				{
					coordinates[0],
					coordinates[1]
				});
			}
			ILinearRing shell = this._geomFactory.CreateLinearRing(coordinates);
			return this._geomFactory.CreatePolygon(shell, null);
		}

		private static Coordinate[] CleanRing(Coordinate[] original)
		{
			Assert.IsEquals(original[0], original[original.Length - 1]);
			List<Coordinate> list = new List<Coordinate>();
			Coordinate coordinate = null;
			for (int i = 0; i <= original.Length - 2; i++)
			{
				Coordinate coordinate2 = original[i];
				Coordinate coordinate3 = original[i + 1];
				if (!coordinate2.Equals(coordinate3) && (coordinate == null || !ConvexHull.IsBetween(coordinate, coordinate2, coordinate3)))
				{
					list.Add(coordinate2);
					coordinate = coordinate2;
				}
			}
			list.Add(original[original.Length - 1]);
			return list.ToArray();
		}

		private readonly IGeometryFactory _geomFactory;

		private readonly Coordinate[] _inputPts;

		private class RadialComparator : IComparer<Coordinate>
		{
			public RadialComparator(Coordinate origin)
			{
				this._origin = origin;
			}

			public int Compare(Coordinate p1, Coordinate p2)
			{
				return ConvexHull.RadialComparator.PolarCompare(this._origin, p1, p2);
			}

			private static int PolarCompare(Coordinate o, Coordinate p, Coordinate q)
			{
				double num = p.X - o.X;
				double num2 = p.Y - o.Y;
				double num3 = q.X - o.X;
				double num4 = q.Y - o.Y;
				int num5 = CGAlgorithms.ComputeOrientation(o, p, q);
				if (num5 == 1)
				{
					return 1;
				}
				if (num5 == -1)
				{
					return -1;
				}
				double num6 = num * num + num2 * num2;
				double num7 = num3 * num3 + num4 * num4;
				if (num6 < num7)
				{
					return -1;
				}
				if (num6 > num7)
				{
					return 1;
				}
				return 0;
			}

			private readonly Coordinate _origin;
		}
	}
}
